package parallel.project.graph;

import java.awt.Point;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.List;

/**
 * Defines an edge in a {@link Graph}, which has a given numerical 
 * weight.  This can be used in both undirected and directed 
 * {@link Graph}s.  In a directed {@link Graph} the edge originates at
 * the 'first' node (obtained with {@link getFirst()} and ends at the
 * 'second' node (obtained with {@link getSecond()}.  In undirected
 * {@link Graph}s it doesn't matter which is which.
 * <br><br>
 * Edges can cover a certain number of maze grid locations if desired.
 * See the constructor taking a list of {@link Point}s for how these 2D
 * coordinate locations should be added.  The locations considered
 * "covered" by an edge do no include the locations of the {@link Node}s
 * at the end points of the edge.
 * 
 * @author Adam Clayton
 * @author Larry Walters
 */
public class Edge implements Serializable 
{
	/** The {@link Node} the edge starts from (if directed) */
	private Node first;
	
	/** The {@link Node} the edge ends at (if directed) */
	private Node second;
	
	/** Weight of the edge */
	private Double weight;
	
	/** The coordinate locations on a maze grid that are covered by 
	 * this edge */
	private List<Point> locations;
	
	/**
	 * Creates a new edge that starts at the given {@linkplain from} 
	 * {@link Node} and ends at the {@linkplain to} {@link Node}, 
	 * having the given weight, and covering no maze locations.  If the
	 * graph is not supposed to be directed then it does not matter 
	 * which {@link Node} is which.
	 * 
	 * @param from
	 * 		First {@link Node}, in an undirected {@link Graph}, or the
	 * 		start {@link Node}, in a directed {@link Graph}
	 * @param to
	 * 		Second {@link Node}, in an undirected {@link Graph}, or the
	 * 		end {@link Node}, in a directed {@link Graph}
	 * @param weight
	 * 		Numerical weight associated with going from one {@link Node}
	 * 		to the other
	 */
	public Edge(Node from, Node to, Double weight)
	{
		this.first = from;
		this.second = to;
		this.setWeight(weight);
		this.locations = new ArrayList<Point>();
	}
	
	/**
	 * Creates a new edge that starts at the given {@linkplain from} 
	 * {@link Node} and ends at the {@linkplain to} {@link Node}, 
	 * having the given weight, and covering no maze locations.  If the
	 * graph is not supposed to be directed then it does not matter 
	 * which {@link Node} is which.
	 * 
	 * @param from
	 * 		First {@link Node}, in an undirected {@link Graph}, or the
	 * 		start {@link Node}, in a directed {@link Graph}
	 * @param to
	 * 		Second {@link Node}, in an undirected {@link Graph}, or the
	 * 		end {@link Node}, in a directed {@link Graph}
	 * @param weight
	 * 		Numerical weight associated with going from one {@link Node}
	 * 		to the other
	 * @param locs
	 * 		Maze coordinate locations that are covered by this edge,
	 * 		ordered as going from the <code>from</code> {@link Node} to
	 * 		the <code>to</code> {@link Node}; so the location at
	 * 		<code>locs[0]</code> comes right after the <code>from</code>
	 * 		{@link Node}, <code>locs[1]</code> comes next, and so on
	 * 		up till <code>locs[locs.size()-1]</code> which is right
	 * 		before the location of the <code>to</code> {@link Node}.
	 */
	public Edge(Node from, Node to, Double weight, List<Point> locs)
	{
		this.first = from;
		this.second = to;
		this.setWeight(weight);
		this.locations = locs;
	}	
	
	@Override
	public boolean equals(Object o)
	{
		if (!(o instanceof Edge))
			return false;
		Edge other = (Edge)o;
		// check that all parts are equal
		if (!this.first.equals(other.first) ||
			!this.second.equals(other.second)) 
			return false;
		if (this.weight != null)
		{
			if (!this.weight.equals(other.weight))
				return false;
		}
		else
		{
			if (other.weight != null)
				return false;
		}
		if (this.locations != null)
		{
			if (!this.locations.equals(other.locations))
				return false;
		}
		else
		{
			if (other.locations != null)
				return false;
		}
		return true;
	}
	
	/**
	 * Returns the {@link Node} from which the edge originates, in a
	 * directed {@link Graph}.  In an undirected {@link Graph} it is 
	 * just one of the two {@link Node}s.
	 * 
	 * @return
	 * 		The first {@link Node}.
	 */
	public Node getFirst()
	{
		return this.first;
	}

	/**
	 * Returns the maze grid locations covered by this edge
	 * 
	 * @return
	 * 		Locations covered by this edge, ordered from start to end
	 */
	public List<Point> getLocations()
	{
		return this.locations;
	}
	
	/**
	 * Returns the {@link Node} at which the edge ends, in a directed
	 * {@link Graph}.  In an undirected {@link Graph} it is just one of
	 * the two {@link Node}s.
	 * 
	 * @return
	 * 		The second {@link Node}.
	 */
	public Node getSecond()
	{
		return this.second;
	}
	
	/**
	 * Returns the weight associated with this edge.
	 * 
	 * @return
	 * 		Weight of this edge
	 */
	public Double getWeight()
	{
		return this.weight;
	}
	
	/**
	 * Tests if the given {@link Node} is one of the {@link Node}s
	 * related with this edge, either the first or second.
	 * 
	 * @param node
	 * 		The {@link Node} to test if it's one of the two 
	 * 		{@link Node}s associated with this edge
	 * 
	 * @return
	 * 		True, if it is one of the {@link Node}s, false if not
	 */
	public boolean isAssociatedWith(Node node)
	{
		if (first.equals(node) || second.equals(node))
			return true;
		else
			return false;
	}
	
	/**
	 * Returns a new edge which is a concatenation of this edge and
	 * the given one.  The weights and locations are combined and the
	 * start and end nodes chosen to conform with a directed graph as
	 * much as possible.  But if the edges come from the same node, or
	 * go into the same node, then the resulting edge should be
	 * considered bidirectional (essentially undirected).  Note that 
	 * this DOES NOT change either of the edges themselves (this or the
	 * given one), it only returns a new edge that is the combination.
	 * 
	 * @param edge
	 * 		Edge to combine with this edge to result in a the edge
	 * 
	 * @return
	 * 		Combination of this edge and the given edge
	 * @throws GraphException
	 */
	public Edge merge(Edge edge) throws GraphException
	{
		// determine what the new end point nodes are going to be based
		// on which one is the same between the two edges; note that
		// with undirected graphs it doesn't matter cause there is no
		// direction, so it should still work; when combining the
		// locations, add the location of the common node, since merging 
		// and should be getting rid of that node somewhere else
		Node endPointFirst;
		Node endPointSecond;
		// new locations list
		List<Point> newLocations = new ArrayList<Point>();
		// the given edge comes before this one
		if (this.first == edge.second)
		{
			endPointFirst = edge.first;
			endPointSecond = this.second;
			newLocations.addAll(edge.locations);
			newLocations.add(this.first.getLocation());
			newLocations.addAll(this.locations);
		}
		// this edge comes before the given one
		else if (this.second == edge.first)
		{
			endPointFirst = this.first;
			endPointSecond = edge.second;
			newLocations.addAll(this.locations);
			newLocations.add(this.second.getLocation());
			newLocations.addAll(edge.locations);			
		}
		// both edges start at the same node, in a directed graph this
		// now means the edge would be bidirectional, so doesn't matter
		// which is start and which is end
		else if (this.first == edge.first)
		{
			endPointFirst = this.second;
			endPointSecond = edge.second;
			newLocations.addAll(this.reverseList(this.locations));
			newLocations.add(this.first.getLocation());
			newLocations.addAll(edge.locations);
		}
		// both edges end at the same node, in a directed graph this
		// now means the edge would be bidirectional, so doesn't matter
		// which is start and which is end
		else if (this.second == edge.second)
		{
			endPointFirst = this.first;
			endPointSecond = edge.first;
			newLocations.addAll(this.locations);
			newLocations.add(this.second.getLocation());
			newLocations.addAll(this.reverseList(edge.locations));
		}
		// the edges do not a common node, so throw exception
		else
		{
			throw new GraphException("Can't combine edges, since they" +
				" share no common node");
		}
		// combine the weights
		Double newWeight = this.weight + edge.weight;
		
		// create the new edge with the given data
		Edge newEdge = new Edge(endPointFirst,endPointSecond,
							newWeight,newLocations);
		return newEdge;
	}
	
	/**
	 * Returns a list that is the reverse of the given lists
	 * 
	 * @param list
	 * 		List to reverse
	 * @return
	 * 		Reversed version of the given list
	 */
	private <T> List<T> reverseList(List<T> list)
	{
		List<T> revList = new ArrayList<T>();
		for (int i = list.size() - 1; i >= 0; i--)
			revList.add(list.get(i));
		return revList;
	}
	
	/**
	 * Reverses the ordering of the point locations between the two
	 * {@link Node}s of this edge.
	 */
	public void reverseLocations()
	{
		this.locations = this.reverseList(this.locations);
	}	
	
	/**
	 * Sets the weight for this edge to be the given value
	 * 
	 * @param newWeight
	 * 		New weight to associated with this edge
	 */
	public void setWeight(Double newWeight)
	{
		if (newWeight == null)
			this.weight = 0.0;
		else
			this.weight = newWeight;
	}
	
	/**
	 * If the given {@link Node} is the first one (starting one, in a
	 * directed graph} associated with this edge, then this returns the
	 * second node (ending one).  Otherwise, it returns the first one.
	 * 
	 * @param aNode
	 * 		{@link Node} to check against this edge, and if it's the
	 * 		first, returns the second
	 * 
	 * @return
	 * 		Other {@link Node than this one, assuming the given one is 
	 * 		the first
	 */
	public Node getOtherNode(Node aNode){
		if(aNode == first)
			return second;
		else 
			return first;
	}
	
	@Override
	public String toString()
	{
		String ret = first.getName() + " -> " + second.getName() + " ";
		ret += "weight = " + this.weight + " locations = {";
		for (int i = 0; i < this.locations.size() - 1; i++)
			ret += this.locations.get(i).toString() + ",";
		if (this.locations.size() > 0)
		{
			ret += this.locations.get(
					this.locations.size() - 1).toString();
		}
		ret += "}";
		return ret;
	}
}
